package com.hqq.sort.select;

import com.hqq.sort.Sort;

/**
 * SelectionSort
 * 选择排序
 * 原理:
 * 1.找到数组中最小的那个元素 将它和数组的第一个元素交换位置
 * 2.在剩下的元素中找到最小的元素 和第二个元素交换
 * 3.如此往复 直到将整个数组排序
 * 特点:
 * 1.运行时间和输入无关 [一个有序的数组和无序的数组在长度相等的情况下所用的排序时间是相同的]
 * 2.数据的移动是最小的 [交换次数和数组的大小是线性关系]
 * Created by heqianqian on 2017/8/3.
 */
public class SelectionSort extends Sort {

    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            int minIndex = i;//标记最小元素下标
            for (int j = i + 1; j < a.length; j++) {
                if (less(a[j], a[minIndex])) {
                    minIndex = j;
                }
            }
            //将最小的元素和第i个元素交换
            exchange(a, i, minIndex);
        }
    }
}
